package codingforgreat.lchot150;

public class Lc639 {
    public int numDecodings(String s) {
        char[] str = s.toCharArray();
        long[] dp = new long[str.length];
        return (int)(func(str,0,dp) % 1000000007);
    }
    public long func(char[] s,int index,long[] dp){
        long mod = 1000000007;
        if(index == s.length){
            return 1;
        }
        if(s[index] == '0'){
            return 0;
        }
        if (dp[index] != 0) {
            return dp[index];
        }
        if(s[index] != '*'){
            long ways = func(s,index + 1,dp);
            if(index + 1 >= s.length){
                dp[index] = ways % mod;
                return ways % mod;
            }
            if(s[index + 1] != '*'){
                int num = (s[index] - '0') * 10 + (s[index + 1] - '0');
                if(num < 27){
                    ways += func(s,index + 2,dp);
                }
            }else{
                if(s[index] == '1'){
                    ways += 9 * func(s,index + 2,dp);
                }else if(s[index] == '2'){
                    ways += 6 * func(s,index + 2,dp);
                }
            }
            dp[index] = ways % mod;
            return ways % mod;
        }else{
            long ways = 9*func(s,index + 1,dp);
            if(index + 1 >= s.length){
                dp[index] = ways % mod;
                return ways % mod;
            }
            if(s[index + 1] != '*'){
                if((s[index + 1] - '0') <= 6){
                    ways += 2*func(s,index + 2,dp);
                }else{
                    ways += func(s,index + 2,dp);
                }
            }else{//**
                ways += 15 * func(s,index + 2,dp);
            }
            dp[index] = ways % mod;
            return ways % mod;
        }
    }


}
